
#include "RadixTree.h"

RadixTreeNode::RadixTreeNode(const ::std::string& p, WordId id, MatchType mt)
	: m_left( NULL ), m_right( NULL ), m_prefix(p), m_id(id), m_matchtype(mt)
{
}

RadixTreeNode::~RadixTreeNode()
{
	if( m_left != NULL )
	{
		delete m_left;
		m_left = NULL;
	}
	if( m_right != NULL )
	{
		delete m_right;
		m_right = NULL;
	}
}

WordId RadixTreeNode::insert( const ::std::string& word, WordId id, RadixTreeNode::MatchType mt )
{
	if( word.length() == 0 )
		return NotWord;
	
	size_t i = matchPrefix( word );
	if( i == 0 )
	{
		if( m_right != NULL )
			return m_right->insert( word, id, mt );
		else
		{
			m_right = new RadixTreeNode( word, id, mt );
			return id;
		}
	}
	else if( i == m_prefix.length() )
	{
		if( i == word.length() )
		{
			if( m_id == NotWord )
			{
				m_id = id;
				m_matchtype = mt;
				return id;
			}
			else
				return m_id;
		}
		else if( m_left != NULL )
			return m_left->insert( word.substr(i), id, mt );
		else
		{
			m_left = new RadixTreeNode( word.substr(i), id, mt );
			return id;
		}
	}
	else
	{
		if( i == word.length() )
		{
			RadixTreeNode* tnode = new RadixTreeNode( m_prefix.substr(i), m_id, m_matchtype );
			tnode->m_left = m_left;
			m_left = tnode;
			m_id = id;
			m_matchtype = mt;
		}
		else
		{
			RadixTreeNode* tnode = new RadixTreeNode( m_prefix.substr(i), m_id, m_matchtype );
			tnode->m_left = m_left;
			m_left = tnode;
			tnode->m_right = new RadixTreeNode( word.substr(i), id, mt );
			m_id = NotWord;
		}
		m_prefix = word.substr(0, i);
	}
	return id;
}

WordId RadixTreeNode::search( const ::std::string& word )
{
	if( word.length() == 0 )
		return NotWord;

	size_t i = matchPrefix( word );
	if( i == 0 )
	{
		if( m_right != NULL )
			return m_right->search( word );
		else
			return NotWord;
	}
	else if( i == m_prefix.length() )
	{
		if( i != word.length() && m_left != NULL )
		{
			WordId wi = m_left->search( word.substr(i) );
			if( wi != NotWord )
				return wi;
			else if( m_matchtype == RadixTreeNode::MatchPartial )
				return m_id;
			else
				return NotWord;
		}
		else if( m_matchtype == RadixTreeNode::MatchPartial || (i==word.length() && m_matchtype==RadixTreeNode::MatchStrictly) )
			return m_id;
		else
			return NotWord;
	}
	else
		return NotWord;
}

bool RadixTreeNode::check( const ::std::string& word, size_t pos, ::std::string& checkword )
{
	if( word.length() == 0 )
		return false;

	size_t i = matchPrefix( word.substr(pos) );
	if( i == 0 )
	{
		if( m_right != NULL )
			return m_right->check( word, pos, checkword );
		else 
		{
			if( checkword.length()*2 > word.length() )
				return true;
			else
				return false;
		}
	}
	else if( i == m_prefix.length() )
	{
		checkword += m_prefix;
		if( (pos+i) != word.length() && m_left != NULL )
			return m_left->check( word, pos+i, checkword );
		else if( (pos+i) == word.length() )
			return false;
		else
		{
			if( checkword.length()*2 > word.length() )
				return true;
			else
				return false;
		}
	}
	else
	{
		if( checkword.length()*2 > word.length() )
			return true;
		else
			return false;
	}
}

size_t RadixTreeNode::matchPrefix( const ::std::string& word )
{
	size_t i = 0;
	for( ; i < word.length() && word[i] == m_prefix[i]; i++ );
	return i;
}

RadixTree::RadixTree() : m_root_vector()
{
	for( size_t i = 0; i < 128; i++ )
	{
		m_root_vector.push_back( new RadixTreeNode( ::std::string(1, char(i)), NotWord, RadixTreeNode::MatchStrictly ) );
	}
}

RadixTree::~RadixTree()
{
	for( size_t i = 0; i < 128; i++ )
	{
		delete m_root_vector[i];
	}
}

WordId RadixTree::insert( const ::std::string& word, WordId id, RadixTreeNode::MatchType mt )
{
	if( word.length() == 0 )
		return NotWord;
	
	return m_root_vector[word[0]]->insert( word, id, mt );
}

WordId RadixTree::search( const ::std::string& word )
{
	if( word.length() == 0 )
		return NotWord;

	return m_root_vector[word[0]]->search( word );
}

bool RadixTree::check( const ::std::string& word, ::std::string& checkword )
{
	if( word.length() == 0 )
		return false;

	return m_root_vector[word[0]]->check( word, 0, checkword );
}



